import sys

__all__ = ["even_factor", "jacobi"]



lime_length = sys.int_info.bits_per_digit
lime_mask = (1 << lime_length) - 1

def even_factor(n):
    s = 0
    while not n & lime_mask:
        s += lime_length
        n >>= lime_length
    small_s = 0
    small_d = n & lime_mask
    while not small_d & 1:
        small_s += 1
        small_d >>= 1
    return s + small_s, n >> small_s


def jacobi(m, n):
    if m == 0:
        return 0
    elif n == 0:
        if m == 1 or m == -1:
            return 1
        else:
            return 0

    s, x = even_factor(abs(m))
    t, y = even_factor(abs(n))
    if s and t:
        return 0

    k = 1 if n > 0 else -1
    if m < 0 and y & 2:
        k = -k
    if s & 1 and y & 7 in (3, 5):
        k = -k
    if t & 1 and x & 7 in (3, 5):
        k = -k

    if x == y:
        return 0
    elif x > y:
        if 2 & x & y:
            k = -k
        x, y = y, x

    while x:
        if x == 1:
            return k
        if 2 & x & y:
            k = -k
        x, y = y % x, x
        if x == 0:
            return 0
        zero, x = even_factor(x)
        if zero & 1 and y & 7 in (3, 5):
            k = -k
